package BinarySearch;

public class BinarySearchBalance {
  // 最坏情况 O(log(n))
  // 最好情况 O(log(n))  缺点几乎可以忽略
  int fn(int arr[], int target) {
    int i = 0, j = arr.length;
    while (1 < j - i) {
      int mid = (i + j) >>> 1;
      // 平均循环次数减少了, 但最好情况仍是 log(n)
      if (arr[mid] <= target) {
        i = mid;
      } else {
        j = mid;
      }
    }
    if (arr[i] == target) {
      return i;
    }
    return -1;
  }
}
